package demo3;

/**
 * 盛水最多的容器
 */
class Solution {
    public int maxArea(int[] height) {
        int left = 0;
        int right = height.length - 1;
        int max = 0;
        while (left < right) {
            int w = right - left;
            int h = Math.min(height[left], height[right]);
            max = Math.max(max, w * h);
            if (height[left] <= height[right]) {
                left++;
            }else {
                right--;
            }
        }
        return max;
    }

    public int minSubArrayLen(int target, int[] nums) {
        int n = nums.length, sum = 0, len = Integer.MAX_VALUE;
        for (int left = 0, right = 0; right < n; right++) {
            sum += nums[right]; //进窗口
            while (sum >= target) {  //判断
                len = Math.min(len, right -left + 1); //更新结果
                sum -= nums[left];
                left++; //出窗口
            }
        }
        return len == Integer.MAX_VALUE ? 0 : len;
    }
    public int lengthOfLongestSubstring(String s) {
        char[] ss = s.toCharArray();
        int[] hash = new int[128];
        int left = 0, right = 0, n = s.length();
        int ret = 0;
        while (right < n) {
            hash[ss[right]]++; //进入窗口
            while (hash[ss[right]] > 1) { //判断
                hash[ss[left]]--;
                left++; //出窗口
            }
            ret = Math.max(ret, right - left + 1);
            right++;
        }
        return ret;
    }

    /**
     * 最大连续1的个数
     * @param nums
     * @param k
     * @return
     */
    public int longestOnes(int[] nums, int k) {
        int len = 0, n = nums.length, zero = 0;
        for (int left = 0, right = 0; right < n; right++) {
            if (nums[right] == 0) zero++;  //进窗口
            while (zero > k) {  //判断
                if (nums[left++] == 0) zero--; //出窗口
            }
            len = Math.max(len, right - left + 1);  //更新结果
        }
        return len;
    }

    /**
     * 将x减到0的最小操作数
     * @param nums
     * @param x
     * @return
     */
    public int minOperations(int[] nums, int x) {
        int sum = 0, n = nums.length, len = 0;
        for (int a : nums) {
            sum += a;
        }
        int target = sum - x; //处理细节
        if (target < 0) return -1;
        int ret = -1;
        for (int left = 0, right = 0, tmp = 0; right < n; right++) {
            tmp += nums[right]; //进窗口
            while (tmp > target) { //判断
                tmp -= nums[left++]; //出窗口
            }
            if (tmp == target) ret = Math.max(ret, right - left + 1); //更新结果
        }
        if (ret == -1) return ret;
        else return n - ret;
    }

    public void moveZeroes(int[] nums) {
        int n = nums.length;
        for (int cur = 0, dest = -1; cur < n; cur++) {
            if (nums[cur] != 0) {
                int tmp = nums[cur];
                nums[cur] = nums[dest + 1];
                nums[dest + 1] = tmp;
                dest++;
            }
        }
    }

    public void duplicateZeros(int[] arr) {
        int cur = 0, dest = -1, n = arr.length;
        //1.找到复写的位置
        while (cur < n) {
            if (arr[cur] == 0) {
                dest += 2;
            }else {
                dest++;
            }
            if (dest >= n - 1) {
                break;
            }
            cur++;
        }
        //2.处理边界情况
        if (dest == n) {
            arr[n - 1] = 0;
            cur--;
            dest -= 2;
        }
        //3.从后向前完成复写操作
        while (cur >= 0) {
            if (arr[cur] != 0) {
                arr[dest--] = arr[cur--];
            }else {
                arr[dest--] = 0;
                arr[dest--] = 0;
                cur--;
            }
        }
    }

    //求n的每一位数平方和
    public int bitSum(int n) {
        int sum = 0, t = 0;
        while (n > 0) {
            t = n % 10;
            sum += t * t;
            n /= 10;
        }
        return sum;
    }
    public boolean isHappy(int n) {
        int slow = n, fast = bitSum(n);
        while (slow != fast) {
            slow = bitSum(slow);
            fast = bitSum(bitSum(fast));
        }
        return slow == 1;
    }


}

public class Test {
}
